package algorithm.tree;

import algorithm.model.TreeNode;

/**
 * leetcode
 * 112. Path Sum
 *
 * https://leetcode.com/problems/path-sum/
 * Difficulty : Easy
 * Topic: Tree, DFS, Recursive
 *
 * 给一个二叉树，和一个sum目标值。
 * 找出这个树中，是否有从根节点到叶子节点上的和，恰好等于sum。
 *
 * 思路：
 * 递归，很简单
 *
 * Created by yzy on 2020-04-08 18:05
 */
public class PathSum {
    public static void main(String[] args) {
        Integer[] vals = new Integer[]{5,4,8,11,null,13,4,7,2,null,null,null,1};
        TreeNode root = TreeNode.getTreeNode(vals);
        System.out.println(hasPathSum(root, 22));
    }

    /**
     * 递归思路
     * RunTime: 0ms, 100.0%
     * Memory: 39.4MB, 5.88%
     * @param root
     * @param sum
     * @return
     */
    public static boolean hasPathSum(TreeNode root, int sum) {
        if(root==null){
            return false;
        }
        int nextSum = sum - root.val;
        if(nextSum==0 && root.left==null && root.right==null){
            return true;
        }
        return hasPathSum(root.left, nextSum) || hasPathSum(root.right, nextSum);
    }
}
